/**
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package ro.uvt.sp.lp.hw1.beermugs.algorithms;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 
 * @author LP
 *
 *         DFS foloseste un stack (LIFO - last in first out) implementarea de
 *         fata porneste de la root si merge in adancime de la dreapta la stanga
 * 
 *         			  1 
 *         	     7         2
 *         	  8	      6         3
 *              	        5       4    
 *         
 * 
 *         Clasa de fata poate face cuatre atat cu limita cat si fara limita
 */
public class DFSSolverImpl extends Solver {

	/**
	 * daca avem intr-una dintre halbe 2l atunci avem o solutie
	 */
	public boolean isGoal(State state) {
		return (state.getY() == 2 );
	}

	/**
	 * main method pentru rulare standalone
	 * 
	 * @param args
	 */
	public static void main(String args[]) {
		System.out.println("Cautare DFS fara limita\n");
		new DFSSolverImpl().run();
		System.out.println();
		System.out.println();
		System.out.println("Cautare DFS cu limita");
		/**
		 * se poate vedea in consola ca dupa al noulea nivel se gaseste prima solutie
		 * sunt afisati si pasii
		 */
		new DFSSolverImpl().run(9);
		System.out.println();
		System.out.println();
		
		//new DFSSolverImpl().run(55);

	}

	@Override
	public void run() {
		List<State> stack = new ArrayList<State>();
		stack.add(new State(0, 0, null));

		while (stack.size() > 0) {
			State state = stack.remove(stack.size() - 1);

			if (isGoal(state)) {
				//System.out.println("Solution: " + state.getPath());
				System.out.println("Solution: \n");
				this.prettyPrinting(state);
				System.out.println("Solution END===========================================\n");
			} else {
				List<State> successors = expand(state);

				for (int i = 0; i < successors.size(); i++) {
					State child = successors.get(i);
					if (!state.getPath().contains((Object) child)) {
						stack.add(child);
					}
				}
			}
		}

	}

	/**
	 * 
	 */
	@Override
	public void run(int depth) {
		List<State> stack = new ArrayList<State>();
		//se dauga straea initiala, root node 
		stack.add(new State(0, 0, null));
		/**
		 * se porneste cu step sau depth = 1
		 * depth sau step trebuie inteles asa cum este prezentat in descrierea clasei
		 * adica fiecare pas este un pas in adancime   
		 */
		
		int step = 1;
		while (stack.size() > 0 && step <= depth) {
			State state = stack.remove(stack.size() - 1);
			System.out.println("step: " + step);
			if (isGoal(state)) {
				//System.out.println("Solution: " + state.getPath());
				System.out.println("Solution: \n");
				this.prettyPrinting(state);
				System.out.println("Solution END===========================================\n");
			} else {
				//se calculeaza lista de posbili copii pe baa starii curente
				List<State> successors = expand(state);
				
				//se adauga copii in stack pentru testare 
				for (int i = 0; i < successors.size(); i++) {
					State child = successors.get(i);
					//se adauga in stiva daca in lista de copii ai nodului curent nu mai exista acesta 
					if (!state.getPath().contains((Object) child)) {
						stack.add(child);
					}

				}
				step++;// se incrementeaza 
			}
		}
	}

	/**
	 * la fiecare pas se incearca expandarea, gasirea copiilor pe baza starii, a
	 * nodului curent se verifica fiecare din cele 6 operatii posibile
	 */
	@Override
	public List<State> expand(State parent) {

		int x = parent.getX(), y = parent.getY();
		List<State> successors = new ArrayList<State>();

		if (x < 3 && y > 0) {
			State s = new State(x, y, parent);
			FillXfromY fxy = new FillXfromY();
			fxy.excuteOperation(s);
			successors.add(s);
		}
		if (y < 4 && x > 0) { /* transfer amount z from x to y */
			State s = new State(x, y, parent);
			FillYfromX fyx = new FillYfromX();
			fyx.excuteOperation(s);
			successors.add(s);
		}
		if (x > 0) { /* empty x */
			State s = new State(x, y, parent);
			EmptyX ex = new EmptyX();
			ex.excuteOperation(s);
			successors.add(s);
		}
		if (y > 0) { /* empty y */
			State s = new State(x, y, parent);
			EmptyY ey = new EmptyY();
			ey.excuteOperation(s);
			successors.add(s);
		}
		if (x < 3) { /* fill x from tap */
			State s = new State(x, y, parent);
			FillX fx = new FillX();
			fx.excuteOperation(s);
			successors.add(s);
		}
		if (y < 4) { /* fill y from tap */
			State s = new State(x, y, parent);
			FillY fy = new FillY();
			fy.excuteOperation(s);
			successors.add(s);
		}
		return (successors);

	}
	
	public void prettyPrinting(State state){
		Iterator<State> it =state.getPath().iterator();
		while(it.hasNext()){
			System.out.println(it.next().toString());
		}
		
	}

}
